package dp.test140;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/23 10:56
 */
public class Solution3 {

    // 缓存结果
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    List<String> wordDict;
    HashMap<String, List<String>> map = new HashMap<>();

    public List<String> wordBreak(String s, List<String> wordDict) {
        this.wordDict = wordDict;
        for (String t : wordDict) {
            min = Math.min(min, t.length());
            max = Math.max(max, t.length());
        }
        return dfs(s);
    }

    private List<String> dfs(String s) {
        // 如果指定s为空，返回空列表
        if (s.length() == 0) {
            return new ArrayList<>();
        }
        // 如果缓存中有这个字符串， 保存
        if (map.containsKey(s)) {
            return map.get(s);
        }
        // 创建结果集
        List<String> res = new ArrayList<>();
        for (int i = min; i <= max && s.length() - i >= 0; i++) {
            if (wordDict.contains(s.substring(s.length() - i))) {
                if (s.length() - i == 0) {
                    res.add(s.substring(s.length() - i));
                } else {
                    //递归得到剩余字符串的所有组成可能，然后和当前字符串分别用空格连起来加到结果中
                    List<String> temp = dfs(s.substring(0, s.length() - i));
                    for (String t : temp) {
                        res.add(t + " " + s.substring(s.length() - i));
                    }
                }
            }
        }
        //缓存结果
        map.put(s, res);
        return res;
    }
}
